基纳法

詹姆斯-P. 基纳在 1993 年发表于《SIAM 评论》的一篇论文中, 提出了他的评分方法 。类似于其他许多方法, 基纳法利用竞争者（队伍）之间竞争（比赛）的非负统计量, 来为每支队伍产生一个数值评分。在某些行业里, 该评分被称为能力评分。当然, 一 旦为每支队伍给出了一个数值评分, 就自然能根据评分得到队伍排名。

基纳法将给定队伍的评分与该队的绝对实力联系了起来，而绝对实力又依赖于队伍的相对实力一一即相对于其对手实力而言的该队伍的强弱。随着内容的展开, 这一点将变得更为清楚。基纳将一切都植根于两条规则, 也正是它们决定了一支队伍的实力和评分之间的关系。

实力和评分的规则

  1. 一支队伍的实力应根据它与对手之间的相互作用以及对手的实力来加以评判。
  2. 在给定的联赛中, 每支队伍的评分应与其实力成正比例关系。更具体来说, 如果 $s_i$ 和 $r_i$ 分别为队伍 $i$ 的实力值和评分值, 则应该存在一个比例常数 $\lambda$ 使得 $s_i=\lambda r_i$, 且对于联赛中的每支队伍而言, $\lambda$ 的值都相等。

选择体现实力的属性

为了将上述两条规则转变为可以用来计算每支队伍的数值评分的机制, 让我们对问题中的某些变量赋予不同的量。首先, 让我们确定所考虑的竞争或体育项目中的某些属性或统计数据, 我们认为在这些属性之上, 可以合理地进行队伍实力的相对比较, 并令 $$ a_{i j}=\text { 队伍 } i \text { 与队伍 } j \text { 竞争时给出的统计数据值 } $$

举例来说, 我们可以考虑使用的最简单的统计数据之一, 就是队伍 $i$ 在本赛季中击败 队伍 $j$ 的次数。对于每个平局, 我们给两支参赛队都赋予 $1 / 2$ 。换而言之, 若 $W_{i j}$ 是队伍 $i$ 最近击败队伍 $j$ 的次数, 且若 $T_{i j}$ 是队伍 $i$ 和 $j$ 战平的次数, 则可以设 $$ a_{i j}=W_{i j}+\frac{T_{i j}}{2} 。 $$

如果你觉得队伍 $i$ 从队伍 $j$ 上所赢取的分数 $S_{i j}$ 是体现 $i$ 相对于 $j$ 的实力的一个更为相 的属性, 则可以定义 $$ a_{i j}=S_{i j} $$

若队伍 $i$ 和 $j$ 交手不止一次, 则 $S_{i j}$ 可以取 $i$ 从 $j$ 所贏得的总的分数。 除了比赛得分和获胜次数外, 你也可以选用其他属性。例如, 如果你是一名老式的大学橄榄球球迷, 并相信更强的队伍是那些在奔跑中胜过他人的队伍, 那么你可能愿意取 $a_{i j}=$ 队伍 $i$ 对队伍 $j$ 所完成的累积冲球码数。

类似地, 一名 NFL 的现代行家则可能认为传球才是最重要的, 此时便有 $a_{i j}=$ 队伍 $i$ 对队伍 $j$ 所完成的传球码数。

不管你选择哪个属性来定义 $a_{i j}$, 你都必须在整个赛季中不断地更新属性数据（当然, 如果你是在所有比赛都已经结束之后才来对联赛进行评价的话, 那就可以不进行更新)。 但是在更新 $a_{i j}$ 时, 你还必须确定一件事, 即某个属性在赛季初的值是否应当与赛季结束 时的值同等重要一一即你是否希望按时间对 $a_{i j}$ 进行加权?

所有这些灵活性使我们可以对排名进行许多变动和微调, 而构建评分和排名模型之所 以如此有趣, 也正是由于这一点。正如你已经开始了解的那样, 基纳法特别适于进行修修补补, 而随着我们介绍的深人, 我们将有更多的机会接触这些方面。

拉普拉斯的承续法则

无论选择了何种属性, 该属性的统计数据都很少能够以原始的形式来产生一种成功的评分方法。例如, 考虑得分 $S_{i j}$ 。如果队伍 $i$ 和 $j$ 都是防守薄弱而进攻出色, 那它们在相互对阵时就都能获得很高的分数。另一方面, 如果队伍 $p$ 和 $q$ 都是防守牢固而进攻乏力, 则 它们之间的比赛就很可能只有很低的分数。如此一来, 在任何后续的评分系统中, 相比于 小的 $S_{p q}$ 和 $S_{q p}$ 值, 大的 $S_{i j}$ 和 $S_{j i}$ 值将对排名产生不适当的影响。当比较队伍 $i$ 和 $j$ 时, 更好 的做法是考虑两队的总得分, 并设 $$ a_{i j}=\frac{S_{i j}}{S_{i j}+S_{j i}} $$ 类似的注意事项对于其他属性也同样成立一一例如, 冲码码数、传球码数、失误次数等。 利用式这样产生的比例 $a_{i j}$ 将比原始值更好, 但正如基纳所指出的, 我们实际上应该使用类似于

$$ a_{i j}=\frac{S_{i j}+1}{S_{i j}+S_{j i}+2} $$

这样的做法。这样做的缘由在于拉普拉斯的承续法则, 其直观思路是, 如果 $$ p_{i j}=\frac{S_{i j}}{\left(S_{i j}+S_{j i}\right)} \text {, 则 } 0 \leqslant p_{i j} \leqslant 1 $$

且 $p_{i j}$ 可以被解释为队伍 $i$ 在今后击败队伍 $j$ 的概率。如果队伍 $i$ 在过去的比赛中以累积总分 $X$ 比 0 击败了队伍 $j$ (其中 $X>0$ ), 则可以合理地认定队伍 $i$ 在某种程度上强于队伍 $j$ (如果 $X$ 的值较小, 则队伍 $i$ 稍强于 $j$, 而如果 $X$ 的值很大, 则 $i$ 远强于 $j$ )。但是, 无论 $X>0$ 的值是多少, 我们都有 $$ p_{i j}=1 \text { 以及 } p_{j i}=0 \text { 。 } $$ 这意味着队伍 $j$ 在今后根本不可能击败队伍 $i$, 而这显然是不成立的。另一方面, 如果式被解读为队伍 $i$ 在今后击败队伍 $j$ 的概率 $p_{i j}$, 则由式可见 $0<p_{i j}<1$,。此外, 如果 $S_{i j} \approx S_{j i}$, 且都为大值, 则 $p_{i j} \approx 1 / 2$, 但随着分差 $S_{i j}-S_{j i}>0$ 增加, $p_{i j}$ 变得更接近于 1 , 这也是合理的。

有所偏好, 还是不要偏好

偏好考虑的是如何补偿 “我们就是行” 的情况, 此时强队将毫不手软地在较弱的对手身上捞取大把的分数, 这么做或者是为了提高自身的评分, 或者就是想 “落井下石”。如 果使用式, 则基纳建议对每个 $a_{i j}$ 采用一个非线性的偏好函数, 如 $$ h(x)=\frac{1}{2}+\frac{\operatorname{sgn}\{x-(1 / 2)\} \sqrt{|2 x-1|}}{2} $$ 以帮助减小强弱之间的差距。换而言之, 就是以 $h\left(a_{i j}\right)$ 来代替 $a_{i j} \circ h(x)$ 的曲线如下图所示,

可以发现该函数具有以下性质, 即 $h(0)=0, h(1)=1$, 且 $h(1 / 2)=1 / 2$ 。使用 $h\left(a_{i j}\right)$ 来代替 $a_{i j}$, 可以带来我们所希望的效果，即最强者和最弱者之间差距不那么极端。 利用 $h(x)$ 实现的偏好, 在值 $1 / 2$ 附近还造成了对两个原始值之间差距的人为拉大, 在区 分实力接近的队伍时, 这可能将有所帮助。

一旦你了解了刚才的式子中基纳的偏好函数并用过一遍以后, 就应该能够构造出许多你自已的偏好函数。例如, 你可能希望定制一个偏好函数, 使它的偏好能力较 $h(x)$ 更强或更弱一些, 或者你希望函数对 $a_{i j}$ 值较大的一端的影响与对 $a_{i j}$ 值较小的一端的影响有所 不同。基纳提出的偏好的思路, 其价值在于你能够针对特定赛式的建模需要来“调整”你的系统。偏好只不过是对基纳法进行调整的不计其数的方法中的一种而已。 偏好并非总是必要的。例如, 偏好对参考文献 $[34,35,1]$ 中所研究的 NFL 排名并 没有显著影响。这可能是由于在所考虑的时间段内, 各支 NFL 球队的实力相当均衡, 因此 也就不那么需要进行精细调整。当然, 对于 NCAA 的体育项目或其他竞赛而言, 情况往往 大不相同，因此不要忽视基纳的这个偏好的思路。

规范化

在确定了如何定义非负 $a_{i j}$ 值的属性, 并确定了是否希望通过重定义 $a_{i j} \leftarrow h\left(a_{i j}\right)$ 来使 这些值有所偏好之后, 如果并不是所有队伍都进行了同样多场比赛的话, 那么还需要对 $a_{i j}$ 进行最后一点改动（或者说规范化）。此时, 我们进行如下替换 $$ a_{i j} \leftarrow \frac{a_{i j}}{n_i} \text { （其中, } n_i=\text { 队伍 } i \text { 所进行的比赛场数） } $$ 为了理解这一做法的必要性, 假设我们用 $S_{i j}$ 来按照式定义 $a_{i j}$ 。如果某些队伍比其他队伍比赛了更多场次, 那么它们就有可能获得更多的得分, 从而带来更大的 $a_{i j}$ 值, 而这将影响到最终由 $a_{i j}$ 所导出的任何 “实力” 度量。对于得分之外的其他统计 数据来说, 这一点同样成立一一比方说, 如果使用的统计数据是冲球码数或传球码数的 话, 那么比赛场次更多的队伍就可能累积获得更高的统计数据, 并由此影响由这些统计数 据给出的任何评分。

注意！偏好本身就具有规范化的效果, 因此, 如果使用了偏好函数, 而各队的比赛场数之间的差异又不是很大时, 式可能就并非必需一一而且这时还会面临着数据 “过度规范化”的风险。此外, 针对不同情况，需要不同的规范化策略。利用式是最为简单的做法, 也是一个不错的出发点, 但你可能还需要创造其他的策略并加以实 验, 以获得最优的结果一一这又是一个可以进行调整的地方。

先有鸡, 还是先有蛋

一旦定义了 $a_{i j}$ 并对其进行了偏好和规范化后, 就可以将数据组织为一个方阵的形式 $\boldsymbol{A}=\left[a_{i j}\right]_{m \times m}$ (其中, $m=$ 联赛中队伍的数量）。

将数据以这种方式加以表达, 可以使我们运用矩阵论中某些极其有力的思路来量化 “实力”并产生数值评分。尽管现在看来还不明显, 但有必要指出, 每支队伍的 “实力值” 和它的 “评分值”之间有着微妙的区别。在后文中, 这一区别将变得越发明显。尽管 “实力值” 和“评分值” 并非等同, 但它们显然是有所关联的。这就将我们带人了一个先有鸡还是先有蛋的境地, 因为我们希望用“评分值” 来衡量 “实力值”, 但每支队伍的 “实力” 又会影响队伍的“评分”。

评分

让我们不管那么多, 干脆闭着眼睛随便选一个, 就从评分开始吧。我们希望在当前赛季中的某个时刻 $t$, 根据这 $m$ 支队伍中每支队伍的、我们所认为的 “实力” (我们现在仍然还不知道它到底是什么）来构建出队伍的评分值。令 $r_j(t)=$ 队伍 $j$ 在时刻 $t$ 的量化评分, 并令 $\boldsymbol{r}(t)$ 表示包含了所有 $m$ 个评分的列向量。可以理解, 评分向量 $\boldsymbol{r}(t)$ 中的每个值 $r_j(t)$ 都会随时间改变, 因此记号中明确表示出的时间其实可以省略一一即我们简单地用 $r_j$ 来代 替 $r_j(t)$, 并设 $$ \boldsymbol{r}=\left(\begin{array}{c} r_1 \\ r_2 \\ \vdots \\ r_m \end{array}\right)=\text { 评分向量。 } $$

尽管 $\boldsymbol{r}$ 中的值现在对我们而言是末知的, 但我们仍假设它们存在且可能通过某种方式加以 确定。

实力

现在我们把式中（目前仅在理论上存在）的评分与“实力” 的概念联系起来。回忆一下，基纳的第一条规则指出, 一支队伍的实力应该由它与对手比赛的表现加以衡量, 同时根据对手的实力加以调整。换而言之, 赢得十场轻而易举的较量, 应该与贏得 十场与强手的比赛要有所区别。

队伍 $i$ 对阵队伍 $j$ 的表现如何, 正是我们希望统计数据 $a_{i j}$ 加以衡量的东西, 而队伍 $j$ 到底多强（或弱）则是我们希望评分值 $r_j$ 加以衡量的东西。因此, 采用如下的定义是合理的。

相对实力

队伍 $i$ 相比于队伍 $j$ 的相对实力定义为 $$ s_{i j}=a_{i j} r_j \circ $$ 我们很自然地把队伍 $i$ 的总实力或绝对实力取为队伍 $i$ 与联盟中所有其他队伍相比的 相对实力之和。换而言之, 可以合理地定义绝对实力（或简称实力）如下。

绝对实力

队伍 $i$ 的绝对实力 (或简称实力) 定义为 $$ s_i=\sum_{j=1}^m s_{i j}=\sum_{j=1}^m a_{i j} r_j \text {, 且 } s=\left(\begin{array}{c} s_1 \\ s_2 \\ \vdots \\ s_m \end{array}\right) \text { 为实力向量。 } $$ 注意, 实力向量 $s$ 可以表示为 $$ s=\left(\begin{array}{c} \sum_j a_{1 j} r_j \\ \sum_j a_{2 j} r_j \\ \vdots \\ \sum_j a_{m j} r_j \end{array}\right)=\left(\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 m} \\ a_{21} & a_{22} & \cdots & a_{2 m} \\ \vdots & \vdots & & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m m} \end{array}\right)\left(\begin{array}{c} r_1 \\ r_2 \\ \vdots \\ r_m \end{array}\right)=\boldsymbol{A} \boldsymbol{r}_{\text {。 }} $$

基本方程

基纳关于实力和评分之间关系的第二条规则, 要求每支队伍的实力和评分成正比例, 即存在一个比例常数 $\lambda$, 使得对于每个 $i$ 都有 $s_i=\lambda r_i$ 。评分向量 $\boldsymbol{r}$ 和实力向量 $\boldsymbol{s}$ 来表达, 则这一规则要求对某个常数 $\lambda$, 有 $s=\lambda \boldsymbol{r}$ 。但是, 式说明 $s=\boldsymbol{A r}$, 因此我们可以得出结论, 即评分向量 $\boldsymbol{r}$ 与矩阵 $\boldsymbol{A}$ 中的统计数据 $a_{i j}$ 可 通过以下方程被联系起来 $$ A r=\lambda r $$ 这一方程就是基纳法的根本! 用线性代数的语言来说, 方程指出评分向量 $\boldsymbol{r}$ 必定是一个特征向量, 而比例常 数 $\lambda$ 必定是矩阵 $\boldsymbol{A}$ 的一个特征值。有关特征值和特征向量的知识, 在因特网上可以找到许多。

乍一看去, 确定评分向量 $\boldsymbol{r}$ 的问题不仅已经解决, 而且式的求解看来出奇的 简单一一只要找到某个矩阵 $\boldsymbol{A}$ 的特征值和特征向量就可以了。但是, 如果我们不能把确定 $\boldsymbol{r}$ 的问题局限为一般特征值问题 $\boldsymbol{A r}=\lambda \boldsymbol{r}$ 的一个特殊的情形的话，那么我们将会遇到麻烦。 其中的原因有很多, 下面就举出若干。

  1. 对于一个一般的 $m \times m$ 矩阵 $\boldsymbol{A}$, 求解式 (4.9) 可以得出多达 $m$ 个不同的 $\lambda$ 值。这 将使我们陷人窘境, 因为我们将不得不从中挑选出一个 $\lambda$ 值。而 $\lambda$ 的选择又会进 而影响所得到的评分向量, 因为一旦 $\lambda$ 确定, 则评分向量 $\boldsymbol{r}$ 将作为方程 $(\boldsymbol{A}-\lambda \boldsymbol{I}) \boldsymbol{r}$ $=0$ 的解而随之确定。
  2. 尽管统计数据矩阵 $\boldsymbol{A}$ 中只包含实数, 但由式（4.9）所得的某些（甚至全部） $\lambda$ 值 则可能是复数, 而这又将使得与之对应的特征向量中包含复数。对于评分和排名而 言, 这样的 $r$ 是毫无用处的。例如, 将一支队伍的评分设为 $6+5 \mathrm{i}$ 而另一支的评分 设为 $6-5 \mathrm{i}$ 是毫无意义的, 因为我们不可能对这两个数进行比较, 并确定谁更大 一些。
  3. 即使在最好的情况下, 求解式得到了实数的 $\lambda$ 值, 但它们还可能是负数。 而哪怕得到了一个正特征值 $\lambda$, 与之相应的特征向量 $\boldsymbol{r}$ 可能（而且也常常会）包含 某些负值元素。虽说负的评分还不至于像复数评分那么糟糕, 但这仍然不是最佳的 结果。
  4. 最后, 我们不得不面对以下问题, 即到底打算如何实际计算出矩阵的特征值和特征 算复杂性将迫使人们去购买或得到用于成熟的特征值计算的软件包的使用权一一而 大多数这样的软件包都如此昂贵, 以至于它们的包装盒上都应该镀上金才配得上那高昂的身价。

佩隆-弗罗贝尼乌斯定理

若 $A_{m \times m} \geqslant \mathbf{0}$ 不可约, 则以下陈述均成立。

资料来源